{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #粉刷房子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #粉刷房子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假如有一排房子，共 <code>n</code> 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。</p>\n",
    "\n",
    "<p>当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个&nbsp;<code>n x 3</code><em>&nbsp;</em>的正整数矩阵 <code>costs</code> 来表示的。</p>\n",
    "\n",
    "<p>例如，<code>costs[0][0]</code> 表示第 0 号房子粉刷成红色的成本花费；<code>costs[1][2]</code>&nbsp;表示第 1 号房子粉刷成绿色的花费，以此类推。</p>\n",
    "\n",
    "<p>请计算出粉刷完所有房子最少的花费成本。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>costs = [[17,2,17],[16,16,5],[14,3,19]]\n",
    "<strong>输出: </strong>10\n",
    "<strong>解释: </strong>将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色<strong>。</strong>\n",
    "&nbsp;    最少花费: 2 + 5 + 3 = 10。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>costs = [[7,6,2]]\n",
    "<strong>输出: 2</strong>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>costs.length == n</code></li>\n",
    "\t<li><code>costs[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= costs[i][j] &lt;= 20</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 256&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/paint-house/\">https://leetcode-cn.com/problems/paint-house/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [JEj789](https://leetcode.cn/problems/JEj789/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [JEj789](https://leetcode.cn/problems/JEj789/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[17,2,17],[16,16,5],[14,3,19]]', '[[7,6,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        r,g,b = 0,0,0\n",
    "        for cost in costs:\n",
    "            _r, _g, _b = r, g, b\n",
    "            r = min(_g, _b)+cost[0]\n",
    "            g = min(_r, _b)+cost[1]\n",
    "            b = min(_r, _g)+cost[2]\n",
    "        return min(r,g,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        l = len(costs)\n",
    "        dp = [\n",
    "            [0, 0, 0] for _ in range(l)\n",
    "        ]\n",
    "        dp[0][0] = costs[0][0]\n",
    "        dp[0][1] = costs[0][1]\n",
    "        dp[0][2] = costs[0][2]\n",
    "\n",
    "        for i in range(1, l):\n",
    "            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]\n",
    "            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]\n",
    "\n",
    "        return min(dp[l-1][0], dp[l-1][1], dp[l-1][2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp = costs[0]\n",
    "        for i in range(1, len(costs)):\n",
    "            dp = [min(dp[j - 1], dp[j - 2]) + c for j, c in enumerate(costs[i])]\n",
    "        return min(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        a,b,c = 0,0,0\n",
    "        for x,y,z in costs:\n",
    "            a,b,c = min(b,c) + x, min(a,c)+y,min(a,b)+z\n",
    "        return min(a,b,c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs):\n",
    "        n = len(costs)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        # 初始化状态数组\n",
    "        dp = [[0] * 3 for i in range(n)]\n",
    "        dp[0] = costs[0]\n",
    "\n",
    "        # 动态规划转移方程\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])\n",
    "            dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])\n",
    "            dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])\n",
    "\n",
    "        # 返回最小的开销\n",
    "        return min(dp[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        n=len(costs)\n",
    "        dp=costs\n",
    "        #dp[0][0]=costs[0][0]\n",
    "        #dp[0][1]=costs[0][1]\n",
    "        #dp[0][2]=costs[0][2]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=min(dp[i-1][1],dp[i-1][2])+costs[i][0]\n",
    "            dp[i][1]=min(dp[i-1][0],dp[i-1][2])+costs[i][1]\n",
    "            dp[i][2]=min(dp[i-1][0],dp[i-1][1])+costs[i][2]\n",
    "        return min(dp[n-1][0],dp[n-1][1],dp[n-1][2]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp = [[0,0,0] for _ in range(len(costs)+1)]\n",
    "        for i in range(1,len(costs)+1):\n",
    "            for j in range(3):\n",
    "                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j-2])+costs[i-1][j]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        return min(reduce(lambda a,b:[min(a[1],a[2])+b[0],min(a[2],a[0])+b[1],min(a[0],a[1])+b[2]],costs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        n=len(costs)\n",
    "        dp=[[0]*3 for _ in range(n)]\n",
    "        dp[0][0]=costs[0][0]\n",
    "        dp[0][1]=costs[0][1]\n",
    "        dp[0][2]=costs[0][2]\n",
    "\n",
    "        for i in range(1,n):\n",
    "            for j in range(3):\n",
    "                index=(j+1)%3\n",
    "                dp[i][j]=min(dp[i-1][j-1],dp[i-1][index])+costs[i][j]\n",
    "        \n",
    "        return min(dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp = [0,0,0]\n",
    "        for i in range(len(costs)):\n",
    "            dp0 = costs[i][0] + min(dp[1], dp[2])\n",
    "            dp1 = costs[i][1] + min(dp[0], dp[2])\n",
    "            dp2 = costs[i][2] + min(dp[0], dp[1])\n",
    "            dp = [dp0, dp1, dp2]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        r,c = len(costs),len(costs[0])\n",
    "        dp = [[0 for _ in range(c)] for _ in range(r)]\n",
    "\n",
    "        dp[0][0] = costs[0][0]\n",
    "        dp[0][1] = costs[0][1]\n",
    "        dp[0][2] = costs[0][2]\n",
    "\n",
    "        for i in range(1,r):\n",
    "            dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + costs[i][0]\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]\n",
    "            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]\n",
    "\n",
    "        return min(dp[r-1][j] for j in range(3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        for i in range(1,len(costs)):\n",
    "            for j in range(3):\n",
    "                costs[i][j] = min(costs[i-1][(j+1)%3]+costs[i][j], costs[i-1][(j+2)%3]+costs[i][j])\n",
    "        return min(costs[-1][0], costs[-1][1], costs[-1][2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        n=len(costs)\n",
    "        dp=[ [0] * 3 for i in range(n)]\n",
    "        dp[0]=[costs[0][0],costs[0][1],costs[0][2]]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=min(dp[i-1][1]+costs[i][0],dp[i-1][2]+costs[i][0])\n",
    "            dp[i][1]=min(dp[i-1][0]+costs[i][1],dp[i-1][2]+costs[i][1])\n",
    "            dp[i][2]=min(dp[i-1][0]+costs[i][2],dp[i-1][1]+costs[i][2])\n",
    "        return min(dp[n-1][0],dp[n-1][1],dp[n-1][2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        r, b, g = costs[0]\n",
    "        for x, y, z in costs[1: ] :\n",
    "            r, b, g = min(b, g) + x, min(r, g) + y, min(r, b) + z\n",
    "        return min(r, b, g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0] # 初始化列表\n",
    "        for i in range (len(costs)): #遍历\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2]) #红色的最小成本\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2]) #蓝色的最小成本\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1]) #绿色的最小成本\n",
    "            dp=[dp0,dp1,dp2] #更新\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]\n",
    "        for i in range(len(costs)):\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])\n",
    "            dp=[dp0,dp1,dp2]\n",
    "        return(min(dp[0],dp[1],dp[2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        # 初始化一个数组，用于存储每种颜色的累计最小花费\n",
    "        dp = [0, 0, 0]\n",
    "\n",
    "        # 遍历每一座房子\n",
    "        for i in range(len(costs)):\n",
    "            # 计算使用每种颜色涂刷当前房子的最小花费\n",
    "            dp0 = costs[i][0] + min(dp[1], dp[2])\n",
    "            dp1 = costs[i][1] + min(dp[0], dp[2])\n",
    "            dp2 = costs[i][2] + min(dp[0], dp[1])\n",
    "\n",
    "            # 更新累计最小花费数组，以便下一次迭代使用\n",
    "            dp = [dp0, dp1, dp2]\n",
    "\n",
    "        # 返回涂刷所有房子的总最小花费\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        a, b, c = costs[0][0], costs[0][1], costs[0][2]\n",
    "        for i in range(1, n):\n",
    "            d = min(b, c) + costs[i][0]\n",
    "            e = min(a, c) + costs[i][1]\n",
    "            f = min(a, b) + costs[i][2]\n",
    "            a = d\n",
    "            b = e\n",
    "            c = f\n",
    "        return min(a, b, c)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        m = len(costs)\n",
    "        n = len(costs[0])\n",
    "        costs_all = copy.copy(costs)\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                costs[i][j] += min([costs[i-1][k] for k in range(n) if k != j])\n",
    "        return min(costs[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        ret_min_cost = [0] * 3\n",
    "        for c_0, c_1, c_2 in costs:\n",
    "            tmp = ret_min_cost\n",
    "            ret_min_cost = list()\n",
    "            ret_min_cost.append(c_0 + min(tmp[1], tmp[2]))\n",
    "            ret_min_cost.append(c_1 + min(tmp[0], tmp[2]))\n",
    "            ret_min_cost.append(c_2 + min(tmp[1], tmp[0]))\n",
    "        return min(ret_min_cost)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        m = len(costs)\n",
    "        n = len(costs[0])\n",
    "        # dp[i][j] = min(dp[i-1][k] + costs[i][j]) k != j\n",
    "\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0] = costs[0]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                dp[i][j] = inf\n",
    "                for k in range(n):\n",
    "                    if k != j:\n",
    "                        dp[i][j] = min(dp[i][j], dp[i-1][k] + costs[i][j])\n",
    "        return min(dp[m-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "         red,blue,green = 0,0,0\n",
    "         for r,b,g in costs:\n",
    "             red,blue,green = min(blue,green) + r, min(red,green) + b, min(red,blue) + g \n",
    "         return min(red,blue,green)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        #相邻的两个房子颜色不能相同。\n",
    "        n = len(costs)\n",
    "        blue = [float(\"inf\") for _ in range(n)]\n",
    "        red = [float(\"inf\") for _ in range(n)]\n",
    "        green = [float(\"inf\") for _ in range(n)]\n",
    "        blue[0] = costs[0][1]\n",
    "        green[0] = costs[0][2]\n",
    "        red[0] = costs[0][0]\n",
    "        for i in range(1, n):\n",
    "            blue[i] = min(red[i-1],green[i-1])+costs[i][1]\n",
    "            red[i]=  min(green[i-1],blue[i-1])+costs[i][0]\n",
    "            green[i] =  min(red[i-1],blue[i-1])+costs[i][2]\n",
    "        return min(blue[n-1],green[n-1],red[n-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]#动态的是每一层的三个值，设置三个值\n",
    "        for  i in range(len(costs)):\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])#选择第零个颜色，加上上一层造价最少的那个\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])#加上蓝色和绿色里最小的\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])\n",
    "            #不停循环\n",
    "            dp=[dp0,dp1,dp2]#设置dp（易于取最小）\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]\n",
    "        for i in range(len(costs)):\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])\n",
    "            dp=[dp0,dp1,dp2]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]\n",
    "        for i in range(len(costs)):\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])\n",
    "            dp=[dp0,dp1,dp2]\n",
    "        return min(dp)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        for i in range(1,len(costs)):\n",
    "            costs[i][0] += min(costs[i-1][1],costs[i-1][2])\n",
    "            costs[i][1] += min(costs[i-1][0],costs[i-1][2])\n",
    "            costs[i][2] += min(costs[i-1][0],costs[i-1][1])\n",
    "        return min(costs[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        #建立动态数组dp[i][j]，其中i表示前i间房子，j表示第i间房子的颜色，dp[i][j]表示当第i间房子为j颜色时前i间粉刷房子所需的最低价格\n",
    "        dp = [[0]*3 for i in range(0, len(costs))]\n",
    "        dp[0][0] = costs[0][0]\n",
    "        dp[0][1] = costs[0][1]\n",
    "        dp[0][2] = costs[0][2]\n",
    "\n",
    "        for i in range(1, len(costs)):\n",
    "            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]\n",
    "            dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + costs[i][2]\n",
    "        \n",
    "        return min(dp[len(costs) - 1][0], dp[len(costs) - 1][1], dp[len(costs) - 1][2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:   \n",
    "        n = len(costs)\n",
    "        dp = [[0]*3 for _ in range(n)]\n",
    "        if n == 0: return 0\n",
    "        for j in range(3):\n",
    "            dp[0][j] = costs[0][j]\n",
    "        for i in range(1, n):\n",
    "            # 相邻的房子颜色不能相同，所以i号房子只需要和i-1号房子比较就行\n",
    "            dp[i][0] = min(dp[i-1][1]+costs[i][0], dp[i-1][2]+costs[i][0])\n",
    "            dp[i][1] = min(dp[i-1][0]+costs[i][1], dp[i-1][2]+costs[i][1])\n",
    "            dp[i][2] = min(dp[i-1][1]+costs[i][2], dp[i-1][0]+costs[i][2])\n",
    "        return min(dp[-1][0], dp[-1][1], dp[-1][2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        ret_min_cost = costs[0]\n",
    "        for idx in range(1, len(costs)):\n",
    "            tmp = ret_min_cost\n",
    "            ret_min_cost = list()\n",
    "            ret_min_cost.append(costs[idx][0] + min(tmp[1], tmp[2]))\n",
    "            ret_min_cost.append(costs[idx][1] + min(tmp[0], tmp[2]))\n",
    "            ret_min_cost.append(costs[idx][2] + min(tmp[1], tmp[0]))\n",
    "        return min(ret_min_cost)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        m = len(costs)\n",
    "        dp = [[0 for j in range(3)] for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(3):\n",
    "                # 第一行\n",
    "                if i == 0:\n",
    "                    dp[i][j] = costs[i][j]\n",
    "                elif j == 0:\n",
    "                    dp[i][j] = min(dp[i-1][1], dp[i-1][2]) + costs[i][j]\n",
    "                elif j == 2:\n",
    "                    dp[i][j] = min(dp[i-1][0], dp[i-1][1]) + costs[i][j]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][0], dp[i-1][2]) + costs[i][j]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]  #将列表初始化\n",
    "        for i in range (len(costs)):  #循环遍历\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2]) #计算红色最小成本\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2]) #计算蓝色最小成本\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1]) #计算绿色最小成本\n",
    "            dp=[dp0,dp1,dp2]  #更新列表\n",
    "        return min(dp)  #返回最小成本"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0] #设置初始值\n",
    "        for i in range(len(costs)): #在cost中循环\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2]) #红色的情况\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2]) #绿色的情况\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1]) #蓝色的情况\n",
    "\n",
    "            dp=[dp0,dp1,dp2]\n",
    "        return min(dp) #返回三种情况中最小的一种"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dpr=costs[0][0]\n",
    "        dpg=costs[0][1]\n",
    "        dpb=costs[0][2]\n",
    "        n=len(costs)\n",
    "\n",
    "        for i in range(1,n):\n",
    "            ndpr=min(dpg,dpb)+costs[i][0]\n",
    "            ndpg=min(dpr,dpb)+costs[i][1]\n",
    "            ndpb=min(dpr,dpg)+costs[i][2]\n",
    "\n",
    "            dpr=ndpr\n",
    "            dpg=ndpg\n",
    "            dpb=ndpb\n",
    "        \n",
    "        return min(dpr,dpg,dpb)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        f1, f2, f3 = costs[0][0], costs[0][1], costs[0][2]\n",
    "        for i in range(1, n):\n",
    "            f1, f2, f3 = min(f2, f3) + costs[i][0], min(f1, f3) + costs[i][1], min(f1, f2) + costs[i][2]\n",
    "        return min(f1, f2, f3)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp = [[0, 0, 0] for i in range(len(costs) + 1)]\n",
    "        for i in range(len(costs)):\n",
    "            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0]\n",
    "            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1]\n",
    "            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]\n",
    "        return min(dp[-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        # 初始化动态规划数组，表示涂到当前房屋的最小成本\n",
    "        dp = [0, 0, 0]\n",
    "        \n",
    "        # 遍历每个房屋\n",
    "        for i in range(len(costs)):\n",
    "            # 计算涂当前房屋的各种颜色的成本，并选择最小值\n",
    "            dp0 = costs[i][0] + min(dp[1], dp[2])\n",
    "            dp1 = costs[i][1] + min(dp[0], dp[2])\n",
    "            dp2 = costs[i][2] + min(dp[0], dp[1])\n",
    "            \n",
    "            # 更新动态规划数组为新的成本\n",
    "            dp = [dp0, dp1, dp2]\n",
    "        \n",
    "        # 返回涂完所有房屋的最小成本，即动态规划数组的最小值\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs):\n",
    "        n = len(costs)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        # 初始化状态数组\n",
    "        dp = [[0] * 3 for i in range(n)]\n",
    "        dp[0] = costs[0]\n",
    "\n",
    "        # 动态规划转移方程\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2])\n",
    "            dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2])\n",
    "            dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1])\n",
    "\n",
    "        # 返回最小的开销\n",
    "        return min(dp[n-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, A: List[List[int]]) -> int:\n",
    "        m = len(A)\n",
    "        n = len(A[0])\n",
    "\n",
    "        prev = A[0]\n",
    "        curr = [inf] * n\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                curr[j] = min(prev[k] + A[i][j] if k != j else inf for k in range(n))\n",
    "            prev, curr = curr, prev\n",
    "\n",
    "        return min(prev)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]#设置一个动态值，初始值为0,0,0\n",
    "        for i in range(len(costs)):#i 在每一层（房子）进行循环\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])            \n",
    "            dp=[dp0,dp1,dp2]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        f1, f2, f3 = costs[0][0], costs[0][1], costs[0][2]  #分别代表红蓝绿\n",
    "        for i in range(1, n):\n",
    "            f1, f2, f3 = min(f2, f3) + costs[i][0], min(f1, f3) + costs[i][1], min(f1, f2) + costs[i][2]\n",
    "        return min(f1, f2, f3)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(costs)\n",
    "        dp = [[0 for _ in range(3)] for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0]\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i-1][1]\n",
    "            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i-1][2]\n",
    "        return min(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp = [[0 for _ in range(3)] for _ in range(len(costs))]\n",
    "\n",
    "        for i in range(len(costs)):\n",
    "            for c in range(3):\n",
    "                if i == 0:\n",
    "                    dp[i][c] = costs[i][c]\n",
    "                else:\n",
    "                    if c == 0:\n",
    "                        dp[i][c] = costs[i][c] + min(dp[i-1][1], dp[i-1][2])\n",
    "                    elif c == 1:\n",
    "                        dp[i][c] = costs[i][c] + min(dp[i-1][0], dp[i-1][2])\n",
    "                    else:\n",
    "                        dp[i][c] = costs[i][c] + min(dp[i-1][0], dp[i-1][1])\n",
    "\n",
    "        return min(dp[len(costs) - 1][0], dp[len(costs) - 1][1], dp[len(costs) - 1][2])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]\n",
    "        for i in range(len(costs)):\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])\n",
    "\n",
    "            dp=[dp0,dp1,dp2]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]\n",
    "        for i in range(len(costs)):# 计算涂成红色的最小花费，dp[1]表示前一个房子涂成蓝色的最小花费，dp[2] 表示前一个房子涂成绿色的最小花费。所以当前房子涂成红色的最小花费就是前一个已经是最小花费后的花费。\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])\n",
    "            dp=[dp0,dp1,dp2]#如此遍历，dp0,dp1,dp2一直都是最后一个房子为特定颜色时前几个房子为最小花费时的花\n",
    "        # 最后一个房子的颜色只能是红，蓝，绿之中的一种。所以最后一个房子为这三个颜色的最小花费都已经算出来了，只需要选择其中最小的花费即可\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        r,c = len(costs),len(costs[0])\n",
    "        dp = [[0 for _ in range(c)] for _ in range(r)]\n",
    "\n",
    "        dp[0][0] = costs[0][0]\n",
    "        dp[0][1] = costs[0][1]\n",
    "        dp[0][2] = costs[0][2]\n",
    "\n",
    "        for i in range(1,r):\n",
    "            dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + costs[i][0]\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]\n",
    "            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]\n",
    "\n",
    "        return min(dp[r-1][j] for j in range(3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, A: List[List[int]]) -> int:\n",
    "        m = len(A)\n",
    "        n = len(A[0])\n",
    "\n",
    "        f = [[inf] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 0:\n",
    "                    f[0][j] = A[0][j]\n",
    "                else:\n",
    "                    f[i][j] = min(f[i - 1][k] + A[i][j] if k != j else inf for k in range(n))\n",
    "            \n",
    "        return min(f[m - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]\n",
    "        for i in range(len(costs)):\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])\n",
    "            dp=[dp0,dp1,dp2]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(costs)\n",
    "        dp = [[float(\"inf\"), float(\"inf\"), float(\"inf\")] for _ in range(n)] \n",
    "\n",
    "        dp[0] = costs[0]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(3):\n",
    "                for k in range(3):\n",
    "                    if j != k:\n",
    "                        dp[i][j] = min(costs[i][j] + dp[i - 1][k], dp[i][j]) \n",
    "  \n",
    "    \n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp = [[0,0,0] for _ in range(0,len(costs))]\n",
    "        dp[0] = costs[0]\n",
    "        for i in range(1, len(dp)):\n",
    "            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]\n",
    "            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp = [0,0,0]\n",
    "        for i in range(len(costs)):\n",
    "            dp0 = costs[i][0] + min(dp[1], dp[2])\n",
    "            dp1 = costs[i][1] + min(dp[0], dp[2])\n",
    "            dp2 = costs[i][2] + min(dp[0], dp[1])\n",
    "            dp = [dp0, dp1, dp2]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        \n",
    "        for i in range(1, n) :\n",
    "            \n",
    "            costs[i][0] += min(costs[i-1][1], costs[i-1][2]) \n",
    "            costs[i][1] += min(costs[i-1][0], costs[i-1][2]) \n",
    "            costs[i][2] += min(costs[i-1][1], costs[i-1][0]) \n",
    "\n",
    "        return min(costs[n-1])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        dp = [[0 for _ in range(3)] for _ in range(n)]\n",
    "        dp[0][0] = costs[0][0]\n",
    "        dp[0][1] = costs[0][1]\n",
    "        dp[0][2] = costs[0][2]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]\n",
    "            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]\n",
    "        return min(dp[n-1][j] for j in range(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]\n",
    "        for i in range(len(costs)):\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])\n",
    "\n",
    "            dp=[dp0,dp1,dp2]\n",
    "        return min(dp)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        row, col = len(costs), len(costs[0])\n",
    "\n",
    "        dp = [costs[0]]+[[0]*3 for _ in range(row-1)]\n",
    "\n",
    "        for i in range(1, row):\n",
    "            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]\n",
    "            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        #状态转移方程 j = 0: dp[i][0] = min(dp[i-1][2]+cost[i-1][2],dp[i-1][1]+cost[i-1][1])\n",
    "        n = len(costs)\n",
    "        dp = [[0]*3 for _ in range(n+1)]\n",
    "        # dp[0][0],dp[0][1],dp[0][2] = costs[0][0],costs[0][1],costs[0][2]\n",
    "        for i in range(1,n+1):\n",
    "            dp[i][0] = min(dp[i-1][2]+costs[i-1][2],dp[i-1][1]+costs[i-1][1])\n",
    "            dp[i][1] = min(dp[i-1][2]+costs[i-1][2],dp[i-1][0]+costs[i-1][0])\n",
    "            dp[i][2] = min(dp[i-1][1]+costs[i-1][1],dp[i-1][0]+costs[i-1][0])\n",
    "        return min(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]#初始化最小成本，分别为红色，蓝色和绿色\n",
    "        for i in range(len(costs)):#遍历每一个房子\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])#将当前房子涂成红色的成本为当前成本+前一个房子涂成蓝色或绿色的最小成本\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])#将当前房子涂成蓝色的成本为当前成本+前一个房子涂成红色或绿色的最小成本\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])#将当前房子涂成绿色的成本为当前成本+前一个房子涂成红色或蓝色的最小成本\n",
    "            dp=[dp0,dp1,dp2]#用当前房子的最小成本替代前一个房子的最小成本\n",
    "        return min(dp)#返回最小成本（最后一个房子涂红色/蓝色/绿色）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        dp = [[0]*3 for _ in range(n)]\n",
    "        dp[0][0], dp[0][1], dp[0][2] = costs[0][0],costs[0][1],costs[0][2]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] =  costs[i][0] + min(dp[i-1][1], dp[i-1][2])\n",
    "            dp[i][1] =  costs[i][1] + min(dp[i-1][0], dp[i-1][2])\n",
    "            dp[i][2] =  costs[i][2] + min(dp[i-1][0], dp[i-1][1])\n",
    "        return min(dp[n-1][0],dp[n-1][1],dp[n-1][2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        if len(costs) == 1:\n",
    "            return min(costs[0])\n",
    "        else:\n",
    "            for i in range(1, len(costs)):\n",
    "                costs[i][0] += min(costs[i-1][1], costs[i-1][2])\n",
    "                costs[i][1] += min(costs[i-1][0], costs[i-1][2])\n",
    "                costs[i][2] += min(costs[i-1][0], costs[i-1][1])\n",
    "            return min(costs[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        # dp[i][:] = 把第i个房子粉分别粉刷成三种颜色的最小成本\n",
    "        if len(costs) == 0:\n",
    "            return 0\n",
    "        if len(costs) == 1:\n",
    "            return min(costs[0])\n",
    "        dp = []\n",
    "        dp.append(costs[0])\n",
    "        for i in range(1, len(costs)):\n",
    "            cur = [0] * 3\n",
    "            for j in range(len(cur)):\n",
    "                cur[j] = min(dp[-1][(j+1)%3] + costs[i][j], dp[-1][(j+2)%3] + costs[i][j])\n",
    "            dp.append(cur)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        #定义DP数组\n",
    "        # DP = []\n",
    "        # DP.append(costs[0])\n",
    "\n",
    "        # for i in range(1,len(costs)):\n",
    "        #     tmp = []\n",
    "        #     for j in range(3):\n",
    "        #         tmp.append(min(costs[i][j]+DP[i-1][(j+1)%3],costs[i][j]+DP[i-1][(j-1)%3]))\n",
    "        #     DP.append(tmp)\n",
    "        # return min(DP[-1])\n",
    "\n",
    "        #定义DP list\n",
    "        # DP = []\n",
    "        DP = costs[0]\n",
    "        for i in range(1,len(costs)):\n",
    "            tmp = []\n",
    "            for j in range(3):\n",
    "                tmp.append(min(costs[i][j]+DP[(j+1)%3],costs[i][j]+DP[(j-1)%3]))\n",
    "            DP = tmp.copy()\n",
    "        return min(DP)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        dp = [[0, 0, 0] for _ in range(n)]\n",
    "        dp[0] = costs[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]\n",
    "            dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + costs[i][2]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]\n",
    "        for i in range(len(costs)):\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])\n",
    "\n",
    "            dp=[dp0,dp1,dp2]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int: # 初始化动态规划数组\n",
    "        dp=[0,0,0]\n",
    "        for i in range(len(costs)):# 计算涂成红蓝绿色最小花费\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])\n",
    "            dp=[dp0,dp1,dp2]\n",
    "        return min(dp) #选择其中最小的花费\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]\n",
    "        for i in range(len(costs)):\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])\n",
    "\n",
    "\n",
    "            dp=[dp0,dp1,dp2]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        dp = [[0 for i in range(3)] for j in range(n)]\n",
    "        dp[0][0] = costs[0][0]\n",
    "        dp[0][1] = costs[0][1]\n",
    "        dp[0][2] = costs[0][2]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] = min(dp[i-1][1],dp[i-1][2])  + costs[i][0]\n",
    "            dp[i][1] = min(dp[i-1][0],dp[i-1][2])  + costs[i][1]\n",
    "            dp[i][2] = min(dp[i-1][0],dp[i-1][1])  + costs[i][2]\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]\n",
    "        for i in range(len(costs)):\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])\n",
    "            dp2=costs[i][2]+min(dp[1],dp[0])\n",
    "            dp=[dp0,dp1,dp2]\n",
    "        return min(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        costsSoFar = costs[0]\n",
    "        for i in range(1, len(costs)):\n",
    "            newCosts = [x for x in costs[i]]\n",
    "            newCosts[0] = min(newCosts[0] + costsSoFar[1], newCosts[0] + costsSoFar[2])\n",
    "            newCosts[1] = min(newCosts[1] + costsSoFar[0], newCosts[1] + costsSoFar[2])\n",
    "            newCosts[2] = min(newCosts[2] + costsSoFar[0], newCosts[2] + costsSoFar[1])\n",
    "            costsSoFar = newCosts\n",
    "            # print(costsSoFar)\n",
    "\n",
    "\n",
    "        return min(costsSoFar)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        #0：红 1：蓝 2：绿\n",
    "        n=len(costs)\n",
    "        f=[[0]*3 for _ in range(n)]\n",
    "        f[0][0]=costs[0][0]\n",
    "        f[0][1]=costs[0][1]\n",
    "        f[0][2]=costs[0][2]\n",
    "        #ans=min(f[n])\n",
    "        for i in range(1,n):\n",
    "            r=f[i-1][0]\n",
    "            b=f[i-1][1]\n",
    "            g=f[i-1][2]\n",
    "            f[i][0]=costs[i][0]+min(g,b)\n",
    "            f[i][1]=costs[i][1]+min(r,g)\n",
    "            f[i][2]=costs[i][2]+min(r,b)\n",
    "        return min(f[n-1])\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp = [0,0,0] #设定初始层\n",
    "        for i in range(len(costs)): #让i在房子循环\n",
    "            dp0 = costs[i][0] + min(dp[1],dp[2]) #选红色时\n",
    "            dp1 = costs[i][1] + min(dp[0],dp[2]) #选蓝色时\n",
    "            dp2 = costs[i][2] + min(dp[0],dp[1]) #选绿色时\n",
    "            dp = [dp0,dp1,dp2]\n",
    "        return min(dp) #返回最后一层和中的最小值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        if len(costs) == 1:\n",
    "            return min(costs[0])\n",
    "        dp = [[0,0,0] for _ in range(len(costs))]\n",
    "        dp[0][0],dp[0][1],dp[0][2] = costs[0][0],costs[0][1],costs[0][2]\n",
    "\n",
    "        for i in range(1,len(costs)):\n",
    "            dp[i][0] = min(dp[i-1][1],dp[i-1][2]) + costs[i][0]\n",
    "            dp[i][1] = min(dp[i-1][0],dp[i-1][2]) + costs[i][1]\n",
    "            dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + costs[i][2]\n",
    "            \n",
    "        return min(dp[len(costs)-1][0],dp[len(costs)-1][1],dp[len(costs)-1][2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        self.df_cache = {}\n",
    "        return self.df_helper(costs, 0) \n",
    "\n",
    "    def df_helper(self, costs, n):\n",
    "        mcosts = []\n",
    "        for color in [0, 1, 2]:\n",
    "            xcost = self.df_helper_color(costs, n, color)\n",
    "            mcosts.append(xcost)\n",
    "        return min(mcosts)\n",
    "\n",
    "\n",
    "    def df_helper_color(self, costs, n, color):\n",
    "        cur_cost = costs[n][color]\n",
    "        if n == len(costs) -1:\n",
    "            return cur_cost\n",
    "        if (n, color) in self.df_cache:\n",
    "            return self.df_cache[(n, color)]\n",
    "        remaining_color = {0, 1, 2} - {color}\n",
    "        next_costs = []\n",
    "        for next_color in remaining_color:\n",
    "            x = self.df_helper_color(costs, n+1, next_color)\n",
    "            next_costs.append(x)\n",
    "        opt_cost = min(next_costs[0], next_costs[1])\n",
    "        self.df_cache[(n, color)] = opt_cost + cur_cost\n",
    "        return opt_cost + cur_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        dp = [[0 for _ in range(3)] for _ in range(n)]\n",
    "        dp[0][0] = costs[0][0]\n",
    "        dp[0][1] = costs[0][1]\n",
    "        dp[0][2] = costs[0][2]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]\n",
    "            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]\n",
    "            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]\n",
    "        return min(dp[n-1][j] for j in range(3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        n = len(costs)\n",
    "        red_mcost = [1e6] * n\n",
    "        green_mcost = [1e6] * n\n",
    "        blue_mcost = [1e6] * n\n",
    "\n",
    "        for j in range(n):\n",
    "            if j==0:\n",
    "                red_mcost[j]=costs[j][0]\n",
    "                green_mcost[j] = costs[j][1]\n",
    "                blue_mcost[j] = costs[j][2]\n",
    "            else:\n",
    "                red_mcost[j] = min(green_mcost[j - 1], blue_mcost[j - 1]) + costs[j][0]\n",
    "                green_mcost[j] = min(red_mcost[j - 1], blue_mcost[j - 1]) + costs[j][1]\n",
    "                blue_mcost[j] = min(green_mcost[j - 1], red_mcost[j - 1]) + costs[j][2]\n",
    "        return min(min(red_mcost[-1], green_mcost[-1]), blue_mcost[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0]\n",
    "        for i in range(len(costs)):\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2])\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2])\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1])\n",
    "            dp=[dp0,dp1,dp2]\n",
    "        return min(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, costs: List[List[int]]) -> int:\n",
    "        dp=[0,0,0] # 初始化列表\n",
    "        for i in range (len(costs)): #遍历\n",
    "            dp0=costs[i][0]+min(dp[1],dp[2]) #红色的最小成本\n",
    "            dp1=costs[i][1]+min(dp[0],dp[2]) #蓝色的最小成本\n",
    "            dp2=costs[i][2]+min(dp[0],dp[1]) #绿色的最小成本\n",
    "            dp=[dp0,dp1,dp2] #更新\n",
    "        return min(dp)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
